﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;

namespace TreeLayoutPlayground
{
    class OVPairLayoutEngine : LayoutEngine
    {
        // The given Tree has moved by the given amount
        // so its parent should move by some fraction of that amount
        private void parentShift(Tree tree, int x)
        {
            if (tree.Parent != null)
            {
                Tree parent = tree.Parent;
                int xs = x / parent.NumberOfChildren;
                parent.MyBox.Offset(xs, 0);
                parentShift(parent, xs);
            }
        }

        // Shift a Tree and all its children by the given amount
        // Also shifts the parent to keep things centered
        private void shiftTree(Tree tree, int x, int y)
        {
            Queue<Tree> work = new Queue<Tree>();
            work.Enqueue(tree);
            do
            {
                Tree cur = work.Dequeue();
                cur.MyBox.Offset(x, y);

                foreach (Tree c in cur.Children) { work.Enqueue(c); }
            } while (work.Count > 0);

            parentShift(tree, x);
        }

        private bool findOverlappingPair(List<Tree> nodes, out Tree treeA, out Tree treeB, out Rectangle overlap)
        {
            // Find two nodes that overlap (including the gap)
            for (int a = 0; a < nodes.Count; a++)
            {
                treeA = nodes[a];
                Rectangle ba = Rectangle.Inflate(treeA.MyBox, HalfGap, HalfGap);
                for (int b = a + 1; b < nodes.Count; b++)
                {
                    treeB = nodes[b];
                    Rectangle bb = Rectangle.Inflate(treeB.MyBox, HalfGap, HalfGap);
                    overlap = Rectangle.Intersect(ba, bb);

                    // Does the intersection have any area?
                    if ((overlap.Width * overlap.Height) > 0) { return true; }
                }
            }

            // Nothing intersected
            treeA = null;
            treeB = null;
            overlap = Rectangle.Empty;
            return false;
        }

        public override void Layout(Tree tree)
        {
            List<Tree> nodes = new List<Tree>();
            Queue<Tree> work = new Queue<Tree>();
            work.Enqueue(tree);

            // Create a list of all the nodes in the Tree
            // and reset their positions
            do
            {
                Tree cur = work.Dequeue();
                cur.MyBox.Location = Point.Empty;
                cur.MyRelativeTranslation = Size.Empty;
                nodes.Add(cur);

                foreach (Tree c in cur.Children) { work.Enqueue(c); }
            } while (work.Count > 0);

            // While there are overlapping pairs
            while (true)
            {
                Tree a, b;
                Rectangle ov;
                if (!findOverlappingPair(nodes, out a, out b, out ov)) { break; }

                // Move one of the nodes based on where in the Tree it is
                if (a.TreeDepth > b.TreeDepth)
                {
                    // A should be below B
                    shiftTree(a, 0, ov.Height);
                }
                else if (a.TreeDepth < b.TreeDepth)
                {
                    // A should be above B
                    shiftTree(b, 0, ov.Height);
                }
                else
                {
                    // A and B are on the same level so move one of them right
                    // Move the one that is already rightmost, default to A
                    if (a.MyBox.X < b.MyBox.X)
                    {
                        shiftTree(b, ov.Width, 0);
                    }
                    else
                    {
                        shiftTree(a, ov.Width, 0);
                    }
                }
            }

            // Find the bounding area for all the nodes
            Rectangle bound = new Rectangle(0, 0, 0, 0);
            foreach (Tree t in nodes)
            {
                bound = Rectangle.Union(bound, t.MyBox);
            }

            // Shift everything so the bound has an upper left corner of (0, 0)
            foreach (Tree t in nodes)
            {
                t.MyBox.Offset(-bound.X, -bound.Y);
            }

            tree.OverallSize = new Size(
                1 + bound.Width,
                1 + bound.Height);
        }
    }
}
